#ifndef LINKLIST_H
#define LINKLIST_H
#include <iostream>
#include<string>
#include<QString>
using namespace std;
template <class T>
class LinkNode
{
    template<class U>
    friend class LinkList;
public:
    LinkNode()
    {
        next=NULL;
    }
    T data;
    LinkNode<T>*next;
};
template <class T>
class LinkList
{
public:
    LinkList();
    ~LinkList();
    LinkList<T>&Insert(int k,const T&x);
    bool IsEmpty()const;
    int GetLength()const;
    bool GetData(int k,T&x);
    bool ModifyData(int k,const T&x);
    int Find(const T&x);
    LinkList<T>& DeleteByIndex(int k,  T& x);
    LinkList<T>& DeleteByKey(const T& x, T& y);
    //void OutPut(ostream& out);
    int FindId(QString x);
    int FindName(QString n);
    int FindF(QString a);
    int FindR(QString n);
    int Find_ClassName(QString n);
    int Find_Sex(QString n);

    LinkNode<T>*head;
};
//构造函数
template<class T>
LinkList<T>::LinkList()
{
    head=new LinkNode<T>();
}

//析构函数
template <class T>
LinkList<T>::~LinkList()
{
    T x;
    int len=GetLength();
    for(int i=len;i>=1;i--)
        DeleteByIndex(i,x);
    delete head;
}

//插入新数据元素
template <class T>
LinkList<T>& LinkList<T>::Insert(int k, const T& x)
{
    LinkNode<T>*p=head;
    LinkNode<T>*newNode=new LinkNode<T>;
    newNode->data=x;
    int len=GetLength();
    if (k<1 || k>len+ 1)
        cout << "元素下标越界，添加失败" << endl;
    else
    {
        for (int i =1; i<k; i++)
            p=p->next;
        newNode->next=p->next;
        p->next=newNode;
    }
    return *this;
}

//判断是否为空表
template<class T>
bool LinkList<T>::IsEmpty() const
{
    return head->next==NULL;
}
//求当前表的长度
template<class T>
int LinkList<T>::GetLength() const
{
    int length=0;
    LinkNode<T>*p=head->next;
    while(p)
    {
        length++;
        p=p->next;
    }
    return length;
}

//按位置取元素
template<class T>
bool  LinkList<T>::GetData(int k, T& x)
{
    LinkNode<T>*p=head->next;
    int index=1;
    if (k<1 || k>GetLength())
        return false;
    while(p!=NULL&&index<k)
    {
        index++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        x =p->data;
        return true;
    };
}

//按位置修改元素
template<class T>
bool  LinkList<T>::ModifyData(int k,const  T& x)
{
    LinkNode<T>*p=head->next;
    int index=1;
    if (k<1 || k>GetLength())
        return false;
    while(p!=NULL&&index<k)
    {
        index++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        p->data=x;
        return true;
    };
}

//按关键字查找
template<class T>
int LinkList<T>::Find(const T& x)
{
    LinkNode<T>*p=head->next;
    int index=1;
    while(p!=NULL&&p->data!=x)
    {
        p=p->next;
        index++;
    }
    if(p!=NULL)
        return index;
    else
        return 0;
}

//按位置删除
template<class T>
LinkList<T>& LinkList<T>::DeleteByIndex(int k, T& x)
{
    if (GetData(k, x))
    {
        LinkNode<T>*p=head;
        LinkNode<T>*q=NULL;
        for(int i=1;i<k;i++)
            p=p->next;
        q=p->next;
        p->next=q->next;
        delete q;
    }
    return *this;
}

//按关键字删除
template<class T>
LinkList<T>& LinkList<T>::DeleteByKey(const T& x, T& y)
{
    int index = Find(x);    //得到要删除元素的位置
    if (index != 0)
        return DeleteByIndex(index, y);
    else
    {
        cout << "没有此元素，删除失败";
        return *this;
    }
}

//按学号查找
template<class T>
int LinkList<T>::FindId(QString x)
{
    LinkNode<T>*p=head->next;
    int index=1;
    while(p!=NULL&&(p->data.Number!=x))
    {
        p=p->next;
        index++;
    }
    if(p!=NULL)
        return index;
    else
        return 0;
}
//按姓名查找
template<class T>
int LinkList<T>::FindName(QString n)
{
    LinkNode<T>*p=head->next;
    int index=1;
    while(p!=NULL&&(p->data.Name!=n))
    {
        p=p->next;
        index++;
    }
    if(p!=NULL)
        return index;
    else
        return 0;
}
//按学院查找
template<class T>
int LinkList<T>::FindF(QString b)
{
    LinkNode<T>*p=head->next;
    int index=1;
    while(p!=NULL&&(p->data.Faculty!=b))
    {
        p=p->next;
        index++;
    }
    if(p!=NULL)
        return index;
    else
        return 0;
}
//按宿舍号查找
template<class T>
int LinkList<T>::FindR(QString b)
{
    LinkNode<T>*p=head->next;
    int index=1;
    while(p!=NULL&&(p->data.RoomNu!=b))
    {
        p=p->next;
        index++;
    }
    if(p!=NULL)
        return index;
    else
        return 0;
}
//按班级查找
template<class T>
int LinkList<T>::Find_ClassName(QString b)
{
    LinkNode<T>*p=head->next;
    int index=1;
    while(p!=NULL&&(p->data.ClassNu!=b))
    {
        p=p->next;
        index++;
    }
    if(p!=NULL)
        return index;
    else
        return 0;
}
//按性别查找
template<class T>
int LinkList<T>::Find_Sex(QString b)
{
    LinkNode<T>*p=head->next;
    int index=1;
    while(p!=NULL&&(p->data.Gender!=b))
    {
        p=p->next;
        index++;
    }
    if(p!=NULL)
        return index;
    else
        return 0;
}
#endif
